Insight-The third eye

INTERESTING LINKS

Puzzles

Berkeley Puzzle Page

Turkish Intelligence Portal

Mathematics

Blogs

Questech 11.1 - Solutions
0. The increasing sequence 1, 3, 4, 9, 10, 12, 13… consists of all those positive integers which are powers of 3 or sums of distinct powers of 3. Find the 100^th term of the sequence.

Solution: We observe that when we write 9 we have 2² numbers in the list, when we write 27, that we have 2³ numbers, and so on. When we write 729 we'll have 64 numbers in the list. Now we add the 36^th number from the previous list in order to get an increasing sequence. The 100^th number is 729 + 243 + 9 = 981.

1. Consider N petrol bunks on a circular highway. A car is to start with zero petrol from one of the bunks and travel around the circle, returning to its original point. The petrol is distributed among the bunks in such a way that the total amount of petrol available in all the bunks is exactly sufficient for the car to make a single loop of the highway.
Prove that there always exists a choice of the starting bunk such that the car will be able to complete the loop.

Solution (Inductive):

Fix a direction, say clockwise. Induction: Check that the cases n=1 and n=2 have a solution. Now assume that it is true for n<=k, and check the case n = k+1. Number the stations P₁, ..., P_k, P_k+1 (clockwise).
Let the petrol quantity required for the diistance between P_i and P_i+1 be d_i.
(d_k+1 = d₁). If, for all i, P_i >= d_i, we have no problem. If not, assume that, for some j, P_j < d_j. Now merge P_j-1 and P_j, so that the stations are P₁, P₂, ..., P_j-1, P_j+1, and so on. Update the distances accordingly.
Now, assume there's a clockwise solution. We need to check the (k+1) case
P_j-1 -- d_j-1 --> P_j -- d_j--> P_j+1.
You know that the car can run a distance of d_j-1 + d_j with a quantity of petrol P_j-1 + P_j + what was remaining after the previous bunk. But P_j <d_j. So the quantity of petrol P_j-1 + petrol remaining will take the car at least to the bunk P_j.

2. There are N parking slots numbered 1 to N. There are N cars, labeled C₁ to C_N. Given a sequence {a₁, a₂,…,a_N | 1=< a_i <=N; for 1 <= i <= n}, car C_i goes to the slot numbered a_i and parks the car there if it is not already occupied, otherwise it parks in the next higher unoccupied slot. It can happen that the car never gets to park at any slot.
Find the number of sequences {a₁, a₂,…,a_N | 1=< a_i <=N; for 1 <= i <= n}, such that all cars are parked in some slot.

Solution: Consider N + 1 parking slots arranged on a circle. Let the first slot come after the N + 1^th slot. Now, given any sequence of N numbers satisfying the constraints of the problem, a valid solution can be obtained. One slot out of N + 1 slots will be unoccupied. There are (N + 1)^N solutions to this new problem. Given any solution to this N + 1 slots problem, we can reduce it to an N slot problem by cyclically permuting the sequence so that the unoccupied slot is always the N + 1^th slot. Thus, there are (N + 1)^N/(N + 1) = (N + 1)^N-1solutions.

PREVIOUS PROBLEMS

In this section, you can browse through the problems that have appeared in previous issues of InsIghT, get hints and see the solutions.

Issue 11.1